package leetCode.offer38;

import java.util.ArrayList;
import java.util.List;


public class Solution1 implements Solution{


    @Override
    public String[] permutation(String s) {
        List<String> result = new ArrayList<>();
        if(s.equals("")) result.add("");
        allPermutation(s.toCharArray(),0,s.length()-1,result);
        return result.toArray(new String[0]);
    }

    /**
     * 全排列问题计算方法
     * @param a 目标数组
     * @param start r1 起始位置坐标
     * @param end rn 终止位置坐标
     */
    public static void allPermutation(char[] a,int start,int end,List<String> result) {
        //递归终止条件
        if(start==end){
            result.add(new String(a));
            //System.out.println("得到排列结果："+Arrays.toString(a));
        }
        for(int i=start;i<=end;i++){
            // 过滤掉重复的排列结果
            if(!notEqual(a,start,i)) continue;
            swap(a,start,i);
            allPermutation(a,start+1,end,result);
            swap(a,start,i);
        }
    }

    /**
     * 交换函数，交换数组a中坐标cursor和i的两个元素
     * @param a 目标数组
     * @param cursor 坐标cursor
     * @param i 坐标i
     */
    public static void swap(char[] a,int cursor,int i){
        //System.out.print("交换 "+a[cursor]+" "+a[i]);
        char temp = a[cursor];
        a[cursor]=a[i];
        a[i]=temp;
        //System.out.println("为："+a[cursor]+" "+a[i]);
    }

    /**
     *  判断坐标cursor到i-1位置的元素是否等于i位置的元素
     *  如果存在，则返回false
     * @param a 目标数组
     * @param cursor 起始坐标
     * @param i 终止坐标
     * @return 相等false
     */
    public static boolean notEqual(char[] a,int cursor,int i){
        for(int j=cursor;j<i;j++){
            if(a[j]==a[i]) {
                //System.out.println(a[j]+"=="+a[i]+"跳过重复结果");
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[] nums ={'a','b','c'};
        List<String> result = new ArrayList();
        allPermutation(nums,0,nums.length-1,result);
        System.out.println(result);
    }


}
